DM 5 - Terminale NSI - A rendre le 16 décembre (Correction)

Sujet : Centre Etrangers - Sujet 2 24-NSIJ2G11 juin 2024 - Ex 2 [6 points] : POO récursivité arbres binaires et les systèmes d’exploitation

Partie A

1.La commande Linux pour afficher le contenu du dossier documents est : ls documents.

2.La commande : mv ../../multimedia /home/documents déplace le répertoire multimedia le dossier documents.

L’arborescence devient :
                            home
                            ├── documents
                            │   ├── cours
                            │   ├── administratif
                            │   ├── personnel
                            │   └── multimedia
                            │       ├── images
                            │       └── videos
                            │           └── films

class Arbre:
    def __init__(self, nom, gauche=None, droit=None):
        self.nom = nom
        self.gauche = gauche
        self.droit = droit

    def est_vide(self):
        return self.gauche is None and self.droit is None

    def parcours(self): # question 8
        print(self.nom)
        if self.gauche is not None:
            self.gauche.parcours()
        if self.droit is not None:
            self.droit.parcours()
            
    def parcours_suffixe(self): # question 10
        for f in self.fils:  # Parcourt récursivement les sous-dossiers
            f.parcours_suffixe()
        print(self.nom) 

Le code donné avec la classe Arbre utilise uniquement deux attributs, gauche et droit, pour représenter les sous-dossiers.

Cela limite l’arborescence à deux fils maximum par nœud.

Cependant, dans une structure de fichiers comme celle de la figure 1. Chaque dossier peut avoir un nombre arbitraire de sous-dossiers (par exemple, documents a trois sous-dossiers : cours, administratif, personnel).

Le code ne peut pas gérer cette situation avec seulement deux attributs (gauche, droit).

4. Dans ce type de parcours :

   • On visite la racine en premier.
   • Ensuite, on parcourt récursivement le sous-arbre gauche.
   • Enfin, on parcourt récursivement le sous-arbre droit.

   Le parcours effectué par le code donné est donc un parcours préfixe (ou préordre).
   
   

5. Le parcours en largeur consiste à explorer les nœuds niveau par niveau, de gauche à droite. En utilisant l’arborescence de la figure 1 :

   Niveau 0 : home Niveau 1 : documents, multimedia Niveau 2 : cours, administratif, personnel, images, videos Niveau 3 : films

Résultat du parcours en largeur : home, documents, multimedia, cours, administratif, personnel, images, videos, films.

Partie B

6. Un dossier est considéré vide si sa liste fils est vide.

class Dossier:
    def __init__(self, nom, liste):
        self.nom = nom
        self.fils = liste  # Liste d'objets de type Dossier

    def est_vide(self):
        return len(self.fils) == 0
    
    def parcours(self): # c'est la réponse question 8, parcours en préfixe
        print(self.nom)  # Affiche le nom du dossier courant
        for f in self.fils:  # Parcourt récursivement les sous-dossiers
            f.parcours()
    
    def parcours_suffixe(self): # c'est la réponse question 10, parcours en suffixe
        for f in self.fils:  # Parcourt récursivement les sous-dossiers
            f.parcours_suffixe()
        print(self.nom) # Affiche le nom du dossier courant
    
    def mkdir(self, nom_dossier): # c'est la réponse question 12, création d'un sous-dossier vide
        self.fils.append(Dossier(nom_dossier, []))
        
    def contient(self, nom_dossier): # c'est la réponse question 13, recherche d'un nom de dossier
        if self.nom == nom_dossier:
            return True

        for f in self.fils:
            if f.contient(nom_dossier):  # Appel récursif
                return True

        return False

7. L'instanciation de la variable var_multimedia représente le dossier multimedia de la figure 1 (avec ses sous-dossiers images et videos, et films en sous-dossier de videos), voici le code correspondant :

var_films = Dossier("films", [])
var_videos = Dossier("videos", [var_films])
var_images = Dossier("images", [])
var_multimedia = Dossier("multimedia", [var_images, var_videos])

Explication : L’arborescence de la figure 1 est :

                            home
                            ├── documents
                            │   ├── cours
                            │   ├── administratif
                            │   ├── personnel
                            └── multimedia
                                ├── images
                                └── videos
                                    └── films

Le dossier films est vide, donc sa liste fils est une liste vide [].
Le dossier videos contient films comme sous-dossier.
Le dossier multimedia contient images et videos comme sous-dossiers.

 def parcours(self):
        print(self.nom)  # Affiche le nom du dossier courant
        for f in self.fils:  # Parcourt récursivement les sous-dossiers
            f.parcours()

# Appel de la méthode parcours en préfixe
var_multimedia.parcours()

multimedia
images
videos
films

9. La méthode parcours termine toujours sur une arborescence de fichiers car lorsque la liste fils est vide (cas d’un dossier sans sous-dossier), la boucle for ne s’exécute pas, ce qui stoppe la récursion pour ce chemin.
   
   

    def parcours_suffixe(self):
            for f in self.fils:  # Parcourt récursivement les sous-dossiers
                f.parcours_suffixe()
            print(self.nom) # Affiche le nom du dossier courant

# Appel de la méthode parcours en suffixe
var_multimedia.parcours_suffixe()

images
films
videos
multimedia

11. La Commande UNIX ls affiche uniquement le contenu d’un dossier. Contrairement à la méthode parcours, qui descend récursivement dans les sous-dossiers et les affichent.

    def mkdir(self, nom_dossier):
        self.fils.append(Dossier(nom_dossier, []))

# Exmple d'utilisation :

var_videos.mkdir("documentaires")

# Affichage des sous-dossiers de "videos"
for sous_dossier in var_videos.fils:
    print(sous_dossier.nom)

films
documentaires

13. def contient(self, nom_dossier):
        if self.nom == nom_dossier:
            return True
    
        for f in self.fils:
            if f.contient(nom_dossier):  # Appel récursif
                return True
    
        return False

# # Exmple d'utilisation : Recherche d'un dossier
print(var_videos.contient("films"))           # Résultat : True
print(var_videos.contient("documentaires"))   # Résultat : True
print(var_videos.contient("series"))          # Résultat : False

True
True
False

def trouver_parent(racine, nom_dossier):
    # Parcourt les fils du dossier courant
    for f in racine.fils:
        if f.nom == nom_dossier:  # Si un des fils correspond au dossier recherché
            return racine  # Retourne le dossier courant comme parent
    
    # Recherche récursive dans les sous-dossiers
    for f in racine.fils:
        parent = trouver_parent(f, nom_dossier)
        if parent:  # Si un parent est trouvé dans un sous-arbre
            return parent
    
    # Si le dossier n'est trouvé dans aucun sous-dossier
    return None

# Utilisation de trouver_parent
parent_films = trouver_parent(var_multimedia, "films")
if parent_films:
    print(f"Le parent de 'films' est : {parent_films.nom}")
else:
    print("Le dossier 'films' n'a pas de parent.")

Le parent de 'films' est : videos

class Dossier:
    def __init__(self, nom, fils, parent=None):
        self.nom = nom           # Nom du dossier
        self.fils = fils         # Liste des sous-dossiers
        self.parent = parent     # Référence au dossier parent (par défaut None)

        # Met à jour l'attribut parent pour chaque sous-dossier
        for f in self.fils:
            f.parent = self
            
var_films = Dossier("films", [])
var_videos = Dossier("videos", [var_films])
var_images = Dossier("images", [])
var_multimedia = Dossier("multimedia", [var_images, var_videos])

# Exemple : Trouver le parent d'un dossier
if var_films.parent:
    print(f"Le parent de 'films' est : {var_films.parent.nom}")
else:
    print("Le dossier 'films' n'a pas de parent.")

Le parent de 'films' est : videos